#pragma once

template <typename E>

struct BiTNode
{
    E data;
    BiTNode *lchild, *rchild;
};


template <typename E>
using BiTree = BiTNode<E> *;


template <typename E,typename F>
void Preorder(BiTree<E> T, F visit)
{
    if (T) {
        visit(T->data);
        Preorder(T->lchild, visit);
        Preorder(T->rchild, visit);

    }
}

template <typename E,typename F>
void Inorder(BiTree<E> T, F visit)
{
    if (T) {
        Inorder(T->lchild, visit);
        visit(T->data);
        Inorder(T->rchild, visit);
    }
}

template <typename E,typename F>
void Postorder(BiTree<E> T, F visit)
{
    if (T) {
        Postorder(T->lchild, visit);
        Postorder(T->rchild, visit);
        visit(T->data);
    }
}

template <typename E>
int NodeCount(BiTree<E> T)
{
    if (!T) return 0;
    else {
        auto L = NodeCount(T->lchild);
        auto R = NodeCount(T->rchild);
        return L + R + 1;
    }
}

template <typename E>
int LeafCount(BiTree<E> T)
{
    if (!T) return 0;
    if (!T->lchild && !T->rchild) return 1;
    else {
        auto L = LeafCount(T->lchild);
        auto R = LeafCount(T->rchild);
        return L + R;
    }
}

template <typename E>
int Depth(BiTree<E> T)
{
    if (!T) return 0;
    else {
        auto L = Depth(T->lchild);
        auto R = Depth(T->rchild);
        return L > R ? L + 1 : R + 1;
    }
}

#include <iostream>
using namespace std;

template <typename E>
void Print(BiTree<E> T,char prefix = '=', int level = 0)
{
    if (T) {
        Print(T->rchild, '/',level + 1);
        for (int i = 0; i < level; ++i)
            cout <<"    ";
        cout << prefix << T->data << endl;
        Print(T->lchild, '\\', level + 1);
    }
}

#include <iostream>
using std::cin;
using std::noskipws;

/// 建立二叉树
BiTree<char> CreateBinaryTree()
{
    char c;
    cin >> noskipws >> c;
    if(c == ' ')
         return nullptr;
    else
    {
        auto T = new BiTNode<char>;
        T->data = c;
        T->lchild = CreateBinaryTree();
        T->rchild = CreateBinaryTree();
        return T;
    }
}


///销毁二叉树 Destroy(&T)
template <typename E>
void Destroy(BiTree<E> &T)
{
    if(T){
        Destroy(T->lchild);
        Destroy(T->rchild);
        delete T;
        T = nullptr;
    }
}

//////////////////////////////////
//二叉排序数基本操作

///二叉排序树查找算法 SearchBST(T, e)
template <typename E>
BiTree<E> SearchBST(BiTree<E> T, E e)
{
    if(!T || T->data == e)
          return T;
    else if (e < T->data)
        return SearchBST(T->lchild, e);
    else
         return SearchBST(T->rchild, e);
}

/// 二叉排序树找最小 FindMinBST(T)
template <typename E>
BiTree<E> FindMinBST(BiTree<E> T)
{
    if(T)
       while(T->lchild)
           T = T->lchild;
    return T;
}

///二叉排序树找最大 FindMaxBST(T)
template <typename E>
BiTree<E> FindMaxBST(BiTree<E> T)
{
    if(T)
       while(T->rchild)
           T = T->rchild;
    return T;
}

///二叉排序树插入  InsertBST(&T,e)
template <typename E>
void InsertBST(BiTree<E> &T, E e)
{
    if (T == nullptr)
        T = new BiTNode<E>{e, nullptr, nullptr};
    else if (e < T->data)
         InsertBST(T->lchild, e);
    else if (e > T->data)
          InsertBST(T->rchild, e);
    else  
        ;
}

//////二叉排序树删除 DeleteBST(&T,e)
template <typename E>
void DeleteBST(BiTree<E> &T, E e)
{
    if (T == nullptr)  return;
    else if (e < T->data)
          DeleteBST(T->lchild, e);
    else if (e < T->data)
          DeleteBST(T->rchild, e);
    else { // T->data == e
         if (T->lchild && T->rchild) { // T 有两个子树
            T->data = FindMaxBST(T->lchild)->data;
            DeleteBST(T->lchild, T->data);
         } else { // T 至多有一个子树
             auto oldNode = T;
             T = T->lchild ? T->lchild : T->rchild;
             delete oldNode;
         }
    }
}


